package binaryTree.LayerOrderTraversal;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Node1 {
    public int val;
    public Node1 left;
    public Node1 right;
    public Node1 next;
    public Node1() {}
    public Node1(int _val) {
        val = _val;
    }
    public Node1(int _val, Node1 _left, Node1 _right, Node1 _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

public class Basic166 {
//    填充每个节点的下一个右侧节点指针
public Node1 connect(Node1 root) {
    Queue<Node1> tmpQueue = new LinkedList<Node1>();
    if (root != null) tmpQueue.add(root);
    while (tmpQueue.size() != 0){
        int size = tmpQueue.size();
        Node1 cur = tmpQueue.poll();
        if (cur.left != null) tmpQueue.add(cur.left);
        if (cur.right != null) tmpQueue.add(cur.right);
        for (int index = 1; index < size; index++){
            Node1 next = tmpQueue.poll();
            if (next.left != null) tmpQueue.add(next.left);
            if (next.right != null) tmpQueue.add(next.right);
            cur.next = next;
            cur = next;
        }
    }
    return root;
}
}




